/*
给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。

注意：n 的值小于15000。

示例1:

输入: [1, 2, 3, 4]

输出: False

解释: 序列中不存在132模式的子序列。
示例 2:

输入: [3, 1, 4, 2]

输出: True

解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
示例 3:

输入: [-1, 3, 2, 0]

输出: True

解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].

*/

#include "stdc++.h"

/* 枚举3
时间复杂度：O(nlogN)
空间复杂度：O(n)
*/
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return false;
        }
        // 左侧最小值
        int leftMin = nums[0];
        // 右侧所有元素
        multiset<int> rightAll{};
        for (int k{2}; k < n; ++k) {
            rightAll.insert(nums[k]);
        }

        for (int j{1}; j < n - 1; ++j) {
            if (leftMin < nums[j]) {
                auto it = rightAll.upper_bound((leftMin)); // Search first element that is greater than leftMin
                if (it != rightAll.end() && *it < nums[j]) {
                    return true;
                }
            }
            leftMin = min(leftMin, nums[j]);
            rightAll.erase(rightAll.find(nums[j + 1]));
        }
        return false;
    }
};

/* 枚举1，单调栈
在单调栈中，从栈底到栈顶的元素是严格单调递减的。
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return false;
        }
        stack<int> candidateK{};
        candidateK.push(nums[n - 1]);
        int maxK = INT_MIN; // max_k 记录所有可以真正作为 2 的元素的最大值
        for (int i{n - 2}; i >= 0; --i) {
            // 首先判断 a[i] 是否可以作为 1
            if (nums[i] < maxK) {
                return true;
            }
            // 然后判断 a[i] 是否可以作为 3，以此找出哪些可以真正作为 2 的元素
            while (!candidateK.empty() && nums[i] > candidateK.top()) {
                maxK = candidateK.top();
                candidateK.pop();
            }
            // 将 a[i] 作为 2 的候选元素放入单调栈中。
            // 这里可以进行一个优化，即如果 a[i] ≤ max_k，那么我们也没有必要将 a[i] 放入栈中，
            // 因为即使它在未来被弹出，也不会将 max_k 更新为更大的值。
            if (nums[i] > maxK) {
                candidateK.push(nums[i]);
            }
        }
        return false;
    }
};

/* 枚举2 单调栈 + 二分查找
时间复杂度：O(nlogN)
空间复杂度：O(n)
*/
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        vector<int> candidate_i = {nums[0]};
        vector<int> candidate_j = {nums[0]};

        for (int k = 1; k < n; ++k) {
            auto it_i = upper_bound(candidate_i.begin(), candidate_i.end(), nums[k], greater<int>());
            auto it_j = lower_bound(candidate_j.begin(), candidate_j.end(), nums[k], greater<int>());
            if (it_i != candidate_i.end() && it_j != candidate_j.begin()) {
                int idx_i = it_i - candidate_i.begin();
                int idx_j = it_j - candidate_j.begin() - 1;
                if (idx_i <= idx_j) {
                    return true;
                }
            }
            
            if (nums[k] < candidate_i.back()) {
                candidate_i.push_back(nums[k]);
                candidate_j.push_back(nums[k]);
            }
            else if (nums[k] > candidate_j.back()) {
                int last_i = candidate_i.back();
                while (!candidate_j.empty() && nums[k] > candidate_j.back()) {
                    candidate_i.pop_back();
                    candidate_j.pop_back();
                }
                candidate_i.push_back(last_i);
                candidate_j.push_back(nums[k]);
            }
        }

        return false;
    }
};
